package com.lsa.skienna.challenge.chap11.the111105_CuttingSticks;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Scanner;

public class Main implements Runnable{
    static String lineSep = System.getProperty("line.separator");
    
    static void process(InputStream in, PrintStream out) {
        TaskReader taskReader = new TaskReader(in);
        try {
            Task task;
            while((task = taskReader.nextTask()) != null) {
                out.print(String.format("The minimum cutting is %s.", solve(task)));
                out.print(lineSep);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    static class TaskReader{
        private Scanner scanner;

        TaskReader(InputStream stream) {
            this.scanner = new Scanner(stream);
            scanner.useLocale(Locale.ENGLISH);
        }
        
        Task nextTask() throws IOException {
            Task task = new Task();
            int stickLen = scanner.nextInt();
            if (stickLen == 0) {
                return null;
            }
            
            int numCuts = scanner.nextInt();
            
            task.stickLen = stickLen;
            task.cuts = new Integer[numCuts];
            for (int i = 0; i < numCuts; i++) {
                task.cuts[i] = (Integer)scanner.nextInt();
            }
            
            return task;
        }
    }
    
    static class Task{
        int stickLen;
        Integer[] cuts;
    }
    
    static class State2 {
    	final int fromCut;
    	final int toCut;
    	final int hash;
    	
		State2(int fromCut, int toCut) {
			this.fromCut = fromCut;
			this.toCut = toCut;
			this.hash = hash();
		}

		@Override
		public int hashCode() {
			return hash;
		}

		private int hash() {
			final int prime = 31;
			int result = 1;
			result = prime * result + fromCut;
			result = prime * result + toCut;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			State2 other = (State2) obj;
			if (fromCut != other.fromCut)
				return false;
			if (toCut != other.toCut)
				return false;
			return true;
		}
    }
    
    static class State{
        final int from; // begging of the stick - in stick 'coordinates', including
        final int to;   // end of the stick - in stick 'coordinates', including
        final int fromCut; // begging of the cuts list, including
        final int toCut;   // end of the cuts list, excluding
        private final int hash;
        
        State(int from, int to, int fromCut, int toCut) {
            this.from = from;
            this.to = to;
            this.fromCut = fromCut;
            this.toCut = toCut;
            hash = hash();
        }

        @Override
        public int hashCode() {
            return hash;
        }

        public int hash() {
            final int prime = 31;
            int result = 1;
            result = prime * result + from;
            result = prime * result + fromCut;
            result = prime * result + to;
            result = prime * result + toCut;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            State other = (State) obj;
            if (hash != other.hash) {
                return false;
            }
            if (from != other.from)
                return false;
            if (fromCut != other.fromCut)
                return false;
            if (to != other.to)
                return false;
            if (toCut != other.toCut)
                return false;
            return true;
        }

        @Override
        public String toString() {
            return String.format(
                    "[from=%s, to=%s, fromCut=%s, toCut=%s]", from, to,
                    fromCut, toCut);
        }
    }
    
    /**
     * Storage to reuse solution states.<br>
     * Stores states in 'state to best cut price' form 
     */
    static class States<T>{
        Map<T, Integer> state2Solution = new HashMap<T, Integer>();
        /**
         * @param s
         * @return
         */
        Integer get(T s) {
            return state2Solution.get(s);
        }
        
        void add(T s, int solution) {
            state2Solution.put(s, solution);
        }
    }
    
    private static int solve(Task task) {
    	return invokeSolveDp(task);
//        return invokeSolveRec(task);
//    	return invokeSolveRec2(task);
    }

    public static int invokeSolveDp(Task task) {
        return solveDp2(task.stickLen, Arrays.asList(task.cuts));
    }

    private static int invokeSolveRec(Task task) {
        States<State> states = new States<State>();
        return solveRec(states, new State(0, task.stickLen-1, 0, task.cuts.length), Arrays.asList(task.cuts));
    }
    
    private static int invokeSolveRec2(Task task) {
        States<State2> states = new States<State2>();
        List<Integer> cuts = new CompositedList<Integer>(0, Arrays.asList(task.cuts), task.stickLen);
        return solveRec2(states, new State2(0, cuts.size()-1), cuts);
    }
    
    private static class CompositedList<T> extends AbstractList<T> {
    	private T first;
    	private List<T> middle;
    	private T last;
    	
		public CompositedList(T first, List<T> middle, T last) {
			this.first = first;
			this.middle = middle;
			this.last = last;
		}

		@Override
		public T get(int index) {
			if (index == 0) {
				return first;
			}
			else if (index == size() - 1) {
				return last;
			}
			return middle.get(index-1);
		}

		@Override
		public int size() {
			return middle.size() + 2;
		}
    }
    
    /**
     * Recursive with memoization solution of the task
     * @param states - states storage
     * @param s - state to solve
     * @param cuts - initial cuts array.
     * @return best cutting price
     */
    private static int solveRec(States<State> states, State s, List<Integer> cuts) {
        {
            Integer solution = states.get(s);
            if (solution != null) {
                return solution;
            }
        }
        int from = s.from;
        int to = s.to;
        if (s.fromCut == s.toCut) {
            return 0;
        }
        int len = to - from + 1;
        if (s.fromCut - s.toCut == 1) {
            states.add(s, len);
            return len;
        }
        int best = Integer.MAX_VALUE;
        for (int i = s.fromCut; i < s.toCut; i++) {
            Integer cut = cuts.get(i);
            // , cuts.subList(0, i)  cuts.subList(i+1, cuts.size())
            int score1 = solveRec(states, new State(from, cut-1, s.fromCut, i), cuts);
            int score2 = solveRec(states, new State(cut, to, i+1, s.toCut), cuts);
            int conf = len + score1 + score2;
            if (conf < best) {
                best = conf;
            }
        }
        states.add(s, best);
        return best;
    }
    
    private static int solveDp2(int len, List<Integer> cuts) {
    	{
    		cuts = new CompositedList<Integer>(0, cuts, len);
    	}
        int size = cuts.size();
        int[][] C = new int[size][size];
        // C - best cut order, C[i][j] - using cuts from i to j
        for (int ll = 3; ll <= size; ll++) {
            for (int i = 1; i <= size - ll + 1; i++) {
                int j = i + ll - 1;
                int i0 = i-1;
                int j0 = j-1;
                int best = Integer.MAX_VALUE;
                final int price = cuts.get(j0) - cuts.get(i0);
                for (int k = i0+1; k < j0; k++) {
                    int guess = C[i0][k] + C[k][j0];
                    if (best > guess) {
                        best = guess;
                    }
                }
                C[i0][j0] = best+price;
            }
        }
        return C[0][size-1];
    }
    
    private static int solveRec2(States<State2> states, State2 s, List<Integer> cuts) {
    	{
            Integer solution = states.get(s);
            if (solution != null) {
                return solution;
            }
        }
    	
    	int len = cuts.get(s.toCut) - cuts.get(s.fromCut);
		if (s.toCut - s.fromCut < 2) {
    		return 0;
    	}
    	
    	int best = Integer.MAX_VALUE;
        for (int k = s.fromCut+1; k < s.toCut; k++) {
        	int conf = solveRec2(states, new State2(s.fromCut, k), cuts) + 
        			solveRec2(states, new State2(k, s.toCut), cuts);
        	if (conf < best) {
        		best = conf;
        	}
        }
        best = best + len;
        states.add(s, best);
    	return best;
    }
    
    private static void print(int[][] dp) {
    	for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[i].length; j++) {
				System.out.print(String.format(" %2s", dp[i][j]));
			}
			System.out.println();
		}
    	System.out.println();
    	System.out.println();
    }
    
    private static int solveDp(int len, List<Integer> cuts) {
//        Bounds[][] bounds = new Bounds[len][len];
        int[][] dp = new int[len][len];
//        for (int i = 0; i < len; i++) {
//            for (int j = i; j < len; j++) {
//                bounds[i][j] = findBounds(i, j, cuts);
//            }
//            dp[i][i] = 0; 
//        }
//        printBounds(bounds);
        for (int ll = 2; ll <= len; ll++) {
            for (int i = 1; i <= len - ll + 1; i++) {
                int j = i + ll - 1;
                // i and j is offset 1, so we should use i-1 instead of i, j-1 instead of j
                Bounds b = findBounds(i-1, j-1, cuts);
                if (b.len() > 0) {
                    //int conf = len + solveRec(states, new State(from, cut-1, s.fromCut, i), cuts) + solveRec(states, new State(cut, to, i+1, s.toCut), cuts);
                    int fromCut = b.left;
                    int toCut = b.right;
                    dp[i-1][j-1] = Integer.MAX_VALUE;
                    for (int k = fromCut; k < toCut; k++) {
                        Integer cut = cuts.get(k);
                        int conf = ll + dp[i-1][cut-1] + dp[cut][j-1];
                        if (conf < dp[i-1][j-1]) {
                            dp[i-1][j-1] = conf;
                        }
                    }
                }
            }
        }
        return dp[0][len-1];
    }
    
    private static void printBounds(Bounds[][] bounds) {
        for (int i = 0; i < bounds.length; i++) {
            for (int j = 0; j < bounds[i].length; j++) {
                if (bounds[i][j] == null) {
                    System.out.print(String.format("[l=%2s,r=%2s] ", -1, -1));
                }
                else {
                    System.out.print(bounds[i][j]);
                }
            }
            System.out.println();
        }
    }
    
    static class Bounds{
        int left;
        int right;
        
        Bounds(int left, int right) {
            this.left = left;
            this.right = right;
        }
        
        int len() {
            return right - left;
        }

        @Override
        public String toString() {
            return String.format("[l=%2s,r=%2s] ", left, right);
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + left;
            result = prime * result + right;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Bounds other = (Bounds) obj;
            if (left != other.left)
                return false;
            if (right != other.right)
                return false;
            return true;
        }
    }
    
    static Bounds findBounds(int le, int ri, List<Integer> cuts) {
        int idx = Collections.binarySearch(cuts, le);
        if (idx < 0) {
            idx = -(idx+1);
        }
        else {
            idx++; // index of first element that strictly greater, can be size()
        }
        int left = idx;
        idx = Collections.binarySearch(cuts, ri);
        if (idx < 0) {
            idx = -(idx+1);
            idx--; // index of first element that strictly smaller, can be -1
        }
        
        idx++; // right bound non-inclusive
        
        return new Bounds(left, idx);
    }
    
    
    public static void main(String[] args) {
        new Main().run();
    }
    
    @Override
    public void run() {
        process(System.in, System.out);
    }
}
